//给你一个 m x n 的迷宫矩阵 maze （下标从 0 开始），矩阵中有空格子（用 '.' 表示）和墙（用 '+' 表示）。同时给你迷宫的入口 
//entrance ，用 entrance = [entrancerow, entrancecol] 表示你一开始所在格子的行和列。 
//
// 每一步操作，你可以往 上，下，左 或者 右 移动一个格子。你不能进入墙所在的格子，你也不能离开迷宫。你的目标是找到离 entrance 最近 的出口。出口
// 的含义是 maze 边界 上的 空格子。entrance 格子 不算 出口。 
//
// 请你返回从 entrance 到最近出口的最短路径的 步数 ，如果不存在这样的路径，请你返回 -1 。 
//
// 
//
// 示例 1： 
// 输入：maze = [["+","+",".","+"],[".",".",".","+"],["+","+","+","."]], entrance =
// [1,2]
//输出：1
//解释：总共有 3 个出口，分别位于 (1,0)，(0,2) 和 (2,3) 。
//一开始，你在入口格子 (1,2) 处。
//- 你可以往左移动 2 步到达 (1,0) 。
//- 你可以往上移动 1 步到达 (0,2) 。
//从入口处没法到达 (2,3) 。
//所以，最近的出口是 (0,2) ，距离为 1 步。
// 
//
// 示例 2： 
// 输入：maze = [["+","+","+"],[".",".","."],["+","+","+"]], entrance = [1,0]
//输出：2
//解释：迷宫中只有 1 个出口，在 (1,2) 处。
//(1,0) 不算出口，因为它是入口格子。
//初始时，你在入口与格子 (1,0) 处。
//- 你可以往右移动 2 步到达 (1,2) 处。
//所以，最近的出口为 (1,2) ，距离为 2 步。
// 
//
// 示例 3： 
// 输入：maze = [[".","+"]], entrance = [0,0]
//输出：-1
//解释：这个迷宫中没有出口。
// 
//
// 
//
// 提示： 
//
// 
// maze.length == m 
// maze[i].length == n 
// 1 <= m, n <= 100 
// maze[i][j] 要么是 '.' ，要么是 '+' 。 
// entrance.length == 2 
// 0 <= entrancerow < m 
// 0 <= entrancecol < n 
// entrance 一定是空格子。 
// 
//
// Related Topics 广度优先搜索 数组 矩阵 👍 67 👎 0


package LeetCode.editor.cn;

import java.util.Deque;
import java.util.LinkedList;

/**
 * @author ldltd
 * @date 2023-10-03 18:26:23
 * @description 1926.迷宫中离入口最近的出口
 */
public class NearestExitFromEntranceInMaze{
	 public static void main(String[] args) {
	 	 //测试代码
	 	 Solution solution = new NearestExitFromEntranceInMaze().new Solution();

	 }
	 
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
		 //dfs  深搜，超时
	int [] dx={-1,1,0,0};
	int [] dy={0,0,-1,1};
	int res=100001;
    public int nearestExit1(char[][] maze, int[] entrance) {
			dfs(maze,entrance[0],entrance[1],0);
			return res==100001?-1:res;
    }
	private void dfs(char[][] maze,int x,int y,int path){
		maze[x][y]='+';
		for (int i = 0; i < 4; i++) {
			int posX=x+dx[i];
			int posY=y+dy[i];
			//如果出界了
			if(!isValid(maze,posX,posY)){
				if(path!=0)
					res=Math.min(path,res);
			}else if(maze[posX][posY]=='.'){
				dfs(maze,posX,posY,path+1);
				maze[posX][posY]='.';
			}
		}
	}
	private boolean isValid(char[][] maze,int x,int y){
		return x<maze.length&&y<maze[0].length&&x>=0&&y>=0;
	}
	//bfs
	public int nearestExit(char[][] maze, int[] entrance) {
		Deque<int []>q=new LinkedList<>();
		q.offer(entrance);
		int res=100001;
		maze[entrance[0]][entrance[1]]='0';
		while (!q.isEmpty()){
			int[] poll = q.poll();
			int x=poll[0];
			int y=poll[1];
			int path=maze[x][y]-'0';
			for (int i = 0; i < 4; i++) {
				int posX=x+dx[i];
				int posY=y+dy[i];
				//如果出界了
				if(!isValid(maze,posX,posY)){
					if(path!=0)
						//res=Math.min(path,res);
						//第一次找到出口就可以退出了
						return path;
				}else if(maze[posX][posY]=='.'){
					maze[posX][posY]= (char) (path+1+'0');
					q.offer(new int[]{posX,posY});
				}
			}
		}
		 return res;
	}
}
//leetcode submit region end(Prohibit modification and deletion)

}
